package com.github.hgkmail.hello.leetcode101.pointer.tree;

import com.github.hgkmail.hello.leetcode101.base.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

//hard
//todo 动态规划
public class LC124BinaryTreeMaximumPathSum {
    public void findParent(TreeNode node, Map<TreeNode, TreeNode> parents) {
        if (node==null) {
            return;
        }
        if (!parents.containsKey(node)) {
            parents.put(node, null);
        }
        if (node.left!=null) {
            parents.put(node.left, node);
        }
        if (node.right!=null) {
            parents.put(node.right, node);
        }
    }

    public int findSum(TreeNode node, Set<TreeNode> used) {
        //todo
        return 0;
    }

    public int maxPathSum(TreeNode root) {
        if (root==null) {
            return 0;
        }
        Map<TreeNode, TreeNode> parents=new HashMap<>();
        Set<TreeNode> used=new HashSet<>();
        findParent(root, parents);

        //todo
        return 0;
    }

    public static void main(String[] args) {

    }
}
